package com.multimedia.scala.euler

import scala.annotation.tailrec
/*
Working from left-to-right if no digit is exceeded by the digit to its left
it is called an increasing number;for example, 134468.

Similarly if no digit is exceeded by the digit to
its right it is called a decreasing number; for example, 66420.

We shall call a positive integer that is neither increasing nor decreasing
a "bouncy" number; for example, 155349.

Clearly there cannot be any bouncy numbers below one-hundred,
but just over half of the numbers below one-thousand (525) are bouncy.
In fact, the least number for which the proportion of bouncy numbers first reaches 50% is 538.

Surprisingly, bouncy numbers become more and more common
and by the time we reach 21780 the proportion of bouncy numbers is equal to 90%.

Find the least number for which the proportion of bouncy numbers is exactly 99%.
 */
object Asd112 {
    def main(args : Array[String]) : Unit = {
        @tailrec
        def find(x: BigInt = 100, bouncy: BigInt = 0): BigInt = {
            if ((bouncy*100)/(x-1)==99) return x - 1

            val digits = x.toString().toCharArray
            @tailrec
            def isBounce(i: Int = 1): Boolean = {
                @tailrec
                def increasing(i: Int): Boolean = {
                    if (i>=digits.size) return false
                    if (digits(i-1)>digits(i)) true
                    else increasing(i+1)
                }
                @tailrec
                def decreasing(i: Int): Boolean = {
                    if (i>=digits.size) return false
                    if (digits(i-1)<digits(i)) true
                    else decreasing(i+1)
                }

                if (i>=digits.size) return false
                if (digits(i-1)==digits(i)) isBounce(i+1)
                else if (digits(i-1)<digits(i)) increasing(i+1)
                else decreasing(i+1)
            }
            println(bouncy, x)
            if (isBounce()) find(x+1, bouncy+1)
            else find(x+1, bouncy)
        }
        println(find())
    }
}
